Pascal's Triangle || Pascal's Triangle II

发表于

Pascal’s Triangle

Question

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

1
2
3
4
5
6
7
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
Analysis

利用pre保存上一行的数据，注意循环边界条件的设定

  • 外层循环，i从2开始，由于第一行是从1开始而非0，即此循环应从第二行开始
  • 内层循环，j从1开始，由于每次是j-1与j相加
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result=new ArrayList<>();
        if(numRows<=0)  
            return result;
        List<Integer> pre=new ArrayList<>();
        pre.add(1);
        result.add(pre);
        for(int i=2;i<=numRows;i++){
            List<Integer> cur=new ArrayList<>();
            cur.add(1);
            for(int j=1;j<=pre.size()-1;j++)
                cur.add(pre.get(j-1)+pre.get(j));
            cur.add(1);
            result.add(cur);
            pre=cur;
        }
        return result;
    }
}

Pascal’s Triangle II

Question

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

Analysis

同I，只不过可以采用同一个List保存结果，为了防止上一行的数据被提前覆盖，故从后向前填充当前行的数据

  • j循环从倒数第一个元素也就是i-1开始，而每次填充到当前j的元素是上一行位于j与j-1的元素和
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result=new ArrayList<Integer>();
        if(rowIndex<0)
            return result;
        result.add(1);
        for(int i=1;i<=rowIndex;i++){
            for(int j=i-1;j>0;j--)
                result.set(j,result.get(j)+result.get(j-1));
            result.add(1);
        }
        return result;
    }
}